package com.LeetCode.doublePair;

import org.junit.Test;

import java.util.*;

/**
 * 滑动窗口的最大值
 */
public class maxSlidingWindow {

    /**
     * 自动维护最大值的窗口
     */
    private class MaxQueue{

        Deque<Integer> queue;
        Deque<Integer> maxQueue;
        int capacity;

        public MaxQueue(int k){
            queue = new LinkedList<>();
            maxQueue = new LinkedList<>();
            this.capacity = k;
        }

        public void offer(int x){
            queue.offer(x);
            //容量超过了限制，需要弹出窗口左边的元素，自动维护窗口大小
            if(queue.size() > this.capacity){
                int y = queue.pollFirst();
                if(maxQueue.peekFirst() == y){
                    maxQueue.pollFirst();
                }
            }

            while(maxQueue.size() > 0 && maxQueue.peekLast() < x){
                maxQueue.pollLast();
            }
            maxQueue.offerLast(x);
        }

        public int getMax(){
            return maxQueue.size() > 0 ? maxQueue.peek() : -1;
        }
    }

    public int[] maxSlidingWindow(int[] arr, int k) {
        if(arr == null || arr.length == 0)
            return new int[0];
        int len  = arr.length;

        int[] ans = new int[len - k + 1];
        int index = 0;

        MaxQueue maxQueue = new MaxQueue(k);
        for(int i = 0; i<k; i++){
            maxQueue.offer(arr[i]);
        }

        for(int i = k; i<len; i++){
            ans[index++] = maxQueue.getMax();
            maxQueue.offer(arr[i]);
        }
        ans[index] = maxQueue.getMax();

        return ans;

    }



    @Test
    public void test(){
        int[] arr = {1,3,1,2,0,5};
        int k = 3;
        for(int num : maxSlidingWindow(arr,k)){
            System.out.print(num + " ");
        }
    }
}
